package Class009;

import BasicDataStructures.ListNode;
import Utils.ListUtils;

public class ListReverse {
    public static void main(String[] args) {
        int[] val = {1,2,3,4,5};
        ListNode head = ListUtils.generateList(val);
        ListUtils.printList(head);
        ListNode newHead = reverseListRecursion(head);
        ListUtils.printList(newHead);
        ListNode originHead = reverseListNoRecursion(newHead);
        ListUtils.printList(originHead);
    }



    public static ListNode reverseListNoRecursion(ListNode node) {
        ListNode pre = null;
        ListNode next;
        while(node != null) {
            next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }

    //递归写法
    //函数作用: 反转node及其所有next的节点，返回反转后的链表头
    public static ListNode reverseListRecursion(ListNode node) {
        if(node == null) return null;
        if(node.next == null) return node;
        //先记录下一个节点
        ListNode next = node.next;
        //将当前节点的next指针置空
        node.next = null;
        //让下一个节点去跑递归
        ListNode newHead = reverseListRecursion(next);
        //跑完递归，next及其之后的已经反转完成，把next的next指针连接到当前即可
        next.next = node;
        return newHead;
    }
}
